package leetcode.review;

import org.junit.Test;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @author :songyaozhang
 * @date :Created 2021/8/18 15:17
 * @description :
 */
public class HeapSort {

  @Test
  public void test() {
    int[] nums = {4, 7, 2, 1, 3, 5, 6, 9, 8, 10};
    for (int i = nums.length / 2 - 1; i >= 0; i--) {
      adjust(nums, i, nums.length);
    }
    System.out.println(Arrays.toString(nums));
    for (int i = 0; i < nums.length; i++) {
      int temp = nums[0];
      nums[0] = nums[nums.length - 1 - i];
      nums[nums.length - 1 - i] = temp;
      adjust(nums, 0, nums.length - 1 - i);
    }
    System.out.println(Arrays.toString(nums));
  }

  //构建大顶堆
  public void adjust(int[] nums, int parentIndex, int len) {
    int temp = nums[parentIndex];
    int childIndex = parentIndex * 2 + 1;
    while (childIndex < len) {
      if (childIndex + 1 < len && nums[childIndex + 1] > nums[childIndex]) {
        childIndex++;
      }
      if (temp >= nums[childIndex]) break;
      nums[parentIndex] = nums[childIndex];
      parentIndex = childIndex;
      childIndex = childIndex * 2 + 1;
    }
    nums[parentIndex] = temp;
  }
}
